package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
 *      返回仅包含 1 的最长（连续）子数组的长度。
 *
 * 2. 算法分析
 *      分析：
 *         和往常的滑动窗口问题，设置左右窗口left和right，假设当前的窗口为左
 *         闭右开的区间窗口[left,right),同时设置一个zeros变量记录当前窗口中
 *         的0的个数及一个全局最大长度变量maxLen，具体思路如下：
 *             如果当前右窗口的元素为0，则zeros++，然后移动右窗口，移动之后我需要判断
 *             当前zeros的个数是否超过给定的阈值K，因为题目要求是最多改变K个，所以此时
 *             我们需要移动左窗口，如果此时左窗口的元素为0，则zeros--，这里我们必须使用
 *             循环来处理，直到窗口中的0元素小于等于K，然后更新maxLen即可
 *      上述给出的是滑动窗口的算法实现，下面我们还要给出另外一种思路：前缀和算法实现
 *
 *      前缀和算法思路分析：
 *          注意到如果当前区间[left,right]或者[left,right)中0的个数小于等于K，则当前窗口
 *          长度rigth-left+1或者right-left就是一个有效长度，下面我们以闭区间为例子分析问题
 *          我们需要知道最长的一个，即固定右端点right，找到一个最小的左端点，是得该去区间之间
 *          的0的个数<=K,如何找到区间之间的0的个数就是当前问题的关键，这里我们采用前缀和的方式
 *          设置一个数组P,其中P[i]表示数组A的前i个元素中0的个数，初始化P[0] = (A[0] == 0) ? 1 : 0
 *          则P[i+1]和P[i]之间的关系为：
 *              P[i+1] = P[i]      if  A[i] = 1;
 *              P[i+1] = P[i] + 1  if  A[i] = 0;
 *          有点类似于动态规划的转移方程，不过是一个非常简单的转移方程，扫描完A数组之后我们就求出了
 *          假设当前区间为[left,right],则该区间中的0的个数为P[right] - P[left],这里有一个小的
 *          细节，具体举个例子来看,假设数组A = [1,0,0,1,0,0,1,1,1],P[1] = 1, P[4] = 3,当前
 *          区间[1,4]之间的0的个数为3，但是如果P[4] - P[1] = 2,因为1对应的元素为0，则上述将左
 *          端点的个数减掉了，所以不能直接减，此时需要判断A[left]的元素是否为0，即：
 *              Zeros[left,right] = P[right] - P[left]      if A[left] = 1
 *              Zeros[left,right] = P[right] - P[left] + 1  if A[left] = 0
 *          最后结合数组A和数组P，分析如何求出最长连续1的长度(变化之后的)
 *              可以暴力，但是暴力的时间复杂度比较高为O(n^2),这样就没有得到任何的优化，反而时间
 *              复杂度变高了
 *              换一种思路，当我们固定右边端点right时，我们需要找到最小的一个左边端点left，注意到
 *              P数组是一个单调递增的数组，整个问题可以转化为如下:
 *                  max P[right] - P[left] <= K
 *              则可以使用二分查找算法实现，完整的思路就是：扫描所有可能的右端点，然后通过二分查找
 *              找到最小的左端点，更新maxLen即可
 *              整体的时间复杂度为O(nlogn),这个算法是通过空间换时间(对比与暴力而言)，滑动窗口的
 *              时间O(n),推荐使用滑动窗口的算法解决当前问题
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q020_最大连续1的个数3 {
    // 滑动窗口实现
    public int longestOnes1(int[] A, int K) {
        int n = A.length; // 获取A中的元素个数
        int zeros = 0; // 记录窗口中0的个数
        int left = 0;
        int right = 0;
        int maxLen = 0; // 记录全局最大1长度
        while(right < n) {
            if(A[right] == 0) {
                zeros++;
            }
            right++;
            while(zeros > K) {
                if(A[left] == 0) {
                    zeros--;
                }
                left++;
            }
            maxLen = Math.max(maxLen,right - left);
        }
        return maxLen;
    }

    // 前缀和算法实现
    public int longestOnes2(int[] A, int K) {
        int n = A.length;
        int[] P = new int[n];
        P[0] = A[0] == 1 ? 0 : 1;
        for (int i = 1; i <  n; i++) {
            P[i] = (A[i] == 0) ? P[i-1] + 1 : P[i];
        }
        int maxLen = 0;
        for (int right = A.length -1; right >= 0; right--) {

        }
        return -1;
    }

    // 实现一个二分查找
    public int binarySearch(int[] P,int target) {
        int left = 0;
        int right = P.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if(P[mid] == target) {
                return mid;
            } else if (P[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

}
